package pri.zjy.hash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangjy
 * @description 两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 * <p>
 * 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
 * <p>
 * 你可以按任意顺序返回答案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
 * 示例 2：
 * <p>
 * 输入：nums = [3,2,4], target = 6
 * 输出：[1,2]
 * 示例 3：
 * <p>
 * 输入：nums = [3,3], target = 6
 * 输出：[0,1]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 2 <= nums.length <= 104
 * -109 <= nums[i] <= 109
 * -109 <= target <= 109
 * 只会存在一个有效答案
 * <p>
 * <p>
 * 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
 * @date 2025/2/27 21:25
 */
public class TwoSum_1 {

    public static void main(String[] args) {
        TwoSum_1 twoSum1 = new TwoSum_1();
//        int[] nums = {2, 7, 11, 15};
//        int[] nums = {3, 2, 4};
        int[] nums = {1, 2, 3, 4, 4, 9, 56, 90};
//        int[] nums = {2, 3, 4};
//        int target = 9;
//        int target = 6;
        int target = 8;
//        int target = 6;
//        Arrays.stream(twoSum1.twoSum(nums, target)).forEach(System.out::println);
//        Arrays.stream(twoSum1.twoSum1(nums, target)).forEach(System.out::println);
//        Arrays.stream(twoSum1.twoSum2(nums, target)).forEach(System.out::println);
//        Arrays.stream(twoSum1.twoSum3(nums, target)).forEach(System.out::println);
        Arrays.stream(twoSum1.twoSum4(nums, target)).forEach(System.out::println);
        Arrays.stream(twoSum1.twoSum5(nums, target)).forEach(System.out::println);
    }

    /**
     * 个解：双指针（本题不能使用双指针，因为nums不是有序的）
     * <p>
     * 分析：原数组按非严格递减顺序排列，且target只存在唯一解。
     * <p>
     * 因为初始 i、j 分别指向第一个和最后一个元素，所以对于numbers[i] + numbers[j] = total；
     * 1.若 total>target，由于numbers是递增可重复数组，得出是 j 指向的元素过大，所以 j 左移；
     * 2.若 total<target，同理，是 i 指向元素过小，所以 i 右移。
     * <p>
     * 使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？——答案是不会。
     * <p>
     * 假设 numbers[i]+numbers[j]=target 是唯一解，其中 0≤i<j≤numbers.length−1。
     * 初始时两个指针分别指向下标 0 和下标 numbers.length−1，左指针指向的下标小于或等于 i，右指针指向的下标大于或等于 j。
     * 除非初始时左指针和右指针已经位于下标 i 和 j，否则一定是左指针先到达下标 i 的位置或者右指针先到达下标 j 的位置。
     * <p>
     * 如果左指针先到达下标 i 的位置，此时右指针还在下标 j 的右侧，sum>target，因此一定是右指针左移，左指针不可能移到 i 的右侧。
     * 如果右指针先到达下标 j 的位置，此时左指针还在下标 i 的左侧，sum<target，因此一定是左指针右移，右指针不可能移到 j 的左侧。
     * 由此可见，在整个移动过程中，左指针不可能移到 i 的右侧，右指针不可能移到 j 的左侧，因此不会把可能的解过滤掉。由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。
     */
    public int[] twoSum5(int[] numbers, int target) {
        if (numbers.length == 0) return new int[]{-1, -1};
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int total = numbers[left] + numbers[right];
            if (total < target) {
                // left右移
                left++;
            } else if (total > target) {
                // right左移
                right--;
            } else {
                return new int[]{left + 1, right + 1};
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 个解：遍历+二分查找
     * T(n) = O(nlogn)
     */
    public int[] twoSum4(int[] numbers, int target) {
        if (numbers.length == 0) return new int[]{-1, -1};

        // 本题下标仍然从0开始，不过返回是下标都要+1
        for (int i = 0; i < numbers.length; i++) {
            int remain = target - numbers[i];
            // 二分查找；index1=i，现在要找index2
            // 查找区间为[i+1, numbers.length-1],left随遍历递增；因为原数组递增，前面的数找不到目标值，后面也不用再次判断
            int index2 = binarySearch2(numbers, i + 1, remain);
            if (index2 != -1) return new int[]{i + 1, index2 + 1};
        }
        return new int[]{-1, -1};
    }

    public int binarySearch2(int[] numbers, int startIndex, int target) {
        int left = startIndex, right = numbers.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (numbers[mid] < target) {
                // left右移
                left = mid + 1;
            } else if (numbers[mid] > target) {
                // right左移
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 注意：HashMap的containsKey()时间复杂度为O(1)，put、remove也是
     */
    // 哈希官方解法：边找边存，找不到再存入map，因为题目明确 每种输入只会对应一个答案，且不能使用两次相同的元素
    public int[] twoSum3(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.containsKey(key)) {
                return new int[]{i, map.get(key)};
            }
            // 找不到，才存入map；这样可以避免用到重复元素，且只用一次for循环
            map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    // hashMap 先存哈希表，再找元素
    public int[] twoSum2(int[] nums, int target) {
        // 题目要求 不能使用两次相同元素

        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        // 查找
        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];
            // 同一个元素不能重复使用
            if (map.containsKey(key) && i != map.get(key)) return new int[]{i, map.get(key)};
        }
        return new int[]{-1, -1};
    }

    // 暴力解法
    public int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[]{-1, -1};
    }

    // 错误解法
    public int[] twoSum(int[] nums, int target) {
        // 错误！排序后元素顺序被打乱，返回的下标错误

        // 快排
        Arrays.sort(nums);
        // 单层循环+二分法找target-nums[i]
        // int first = -1， second = -1;
        for (int i = 0; i < nums.length; i++) {
            int second = binarySearch(nums, i, target - nums[i]);
            // first = second == -1 ? -1 : i;
            if (second != -1) {
                return new int[]{i, second};
            }
        }
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int startIndex, int target) {
        // 左闭右闭
        int left = startIndex, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                right = right - 1;
            } else if (target > nums[mid]) {
                left = left + 1;
            } else {
                // startIndex对应元素不能重复用
                return mid == startIndex ? -1 : mid;
            }
        }
        return -1;
    }

}
